class Solution(object):
    def combinationSum3(self, k, n):
        """
        :type k: int
        :type n: int
        :rtype: List[List[int]]
        """
        return_list = []
        now_list = []

        def dfs(value, i, total):
            if i == k - 1:
                if value <= n - total <= 9:
                    now_list.append(n - total)
                    return_list.append(now_list.copy())
                    now_list.pop()
            else:
                min_num = 0
                max_num = 0
                for j in range(k - i):
                    min_num += (value + j)
                    max_num += (9 - j)
                if min_num <= (n - total) <= max_num:
                    for t in range(value, 11 - (k - i)):
                        now_list.append(t)
                        dfs(t + 1, i + 1, total + t)
                        now_list.pop()
        dfs(1, 0, 0)
        return return_list


data = Solution()
k = 4
n = 9
print(data.combinationSum3(k, n))
